import typing
from provate import TreeNode


# 题目：输入两颗二叉树A和B，判断B是不是A的子结构

# 可以分为两步：1：在树1中找到和树2的根节点值一样的节点r；
#             2，判断树1中以r为根节点的子树是不是包含和树2一样的结构

def has_subtree(root1:TreeNode, root2:TreeNode)->bool:

    res = False

    if not root1 and not root2:
        if equal(root1.value, root2.value):
            res = does_tree1_has_tree2(root1, root2)

        if not res:
            res = has_subtree(root1.leftchild, root2)

        if not res:
            res = has_subtree(root1.rightchild, root2)

    return res


def does_tree1_has_tree2(root1:TreeNode, root2:TreeNode)->bool:
    if not root2:
        return True

    if not root1:
        return False

    if not equal(root1.value, root2.value):
        return False

    return does_tree1_has_tree2(root1.leftchild, root2.leftchild) and does_tree1_has_tree2(root1.rightchild, root2.rightchild)


def equal(num1:float, num2:float,e=0.00002)->bool:
    if abs(num1-num2)<e:
        return True
    else:
        return False